package org.example.myleet.p482;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    /**
     * 用数组会更快一些，因为虽然对目标数组都有遍历，但是System.arraycopy会更快
     */
    public String licenseKeyFormatting(String s, int k) {
        char[] charArr = new char[2 * s.length()];
        int l = 2 * s.length() - 1, counter = 0;;
        for (int i = s.length() - 1; i >= 0; --i) {
            char c = s.charAt(i);
            if (c != '-') {
                if (Character.isDigit(c)) {
                    charArr[l] = c;
                } else {
                    charArr[l] = Character.toUpperCase(c);
                }
                --l;
                ++counter;
                if (counter == k) {
                    charArr[l] = '-';
                    --l;
                    counter = 0;
                }
            }
        }
        int end = 2 * s.length() - 1;
        while (l < end && charArr[l + 1] == '-') {
            ++l;
        }
        char[] result = new char[2 * s.length() - 1 - l];
        System.arraycopy(charArr, l + 1, result, 0, 2 * s.length() - 1 - l);
        return new String(result);
    }

    /**
     * 使用链表，比用StringBuilder的insert快
     * 实际上StringBuilder的append完之后reverse更快
     */
//    public String licenseKeyFormatting(String s, int k) {
//        List<Character> charList = new LinkedList<>();
//        int counter = 0;
//        for (int i = s.length() - 1; i >= 0; --i) {
//            char c = s.charAt(i);
//            if (c != '-') {
//                if (Character.isDigit(c)) {
//                    charList.add(0, c);
//                } else {
//                    charList.add(0, Character.toUpperCase(c));
//                }
//                ++counter;
//                if (counter == k) {
//                    charList.add(0, '-');
//                    counter = 0;
//                }
//            }
//        }
//        while (charList.size() > 0 && charList.get(0) == '-') {
//            charList.remove(0);
//        }
//        Iterator<Character> it = charList.iterator();
//        char[] result = new char[charList.size()];
//        for (int i = 0; i < charList.size(); ++i) {
//            result[i] = it.next();
//        }
//        return new String(result);
//    }
}
